Codeforces Round #553 Div2

本场传送门:Round # 533
A. Maxim and Biology
题目大意:给定一个$n$长度的字符串.你可以对这个字符串的任意一个字符进行修改,每次可以把字符往前或往后移动一位,一次修改代价为$1$.我们认为字符表是循环的,即z的后一位是a,a的前一位是z.问:使这个字符串里出现一个子串ATCG的代价最少是多少.
数据范围:$1 \leq n \leq 50$

注意到$n$的范围非常小,故可以直接暴力枚举从每一位开始往后四个字母去修改成ATCG的具体代价是多少,答案自然是其中的最小值.其次考虑每一步的代价怎么计算:由于整个字符表是循环的,所以可以把距离大于$13$的反过来,看做是左边的字母往a的方向走,通过循环路径绕回到右边的字母,注意跨过a和z的时候会有一个额外的代价$1$,如果是按距离来计算的话要补上去.
注意不要修改原有的字符,否则会出锅.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string t = "ACTG";
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	string s;cin >> s;
	int res = 0x3f3f3f3f;
	for(int i = 0;i + 4 <= n;++i)
	{
		int cur = 0;
		for(int j = 0;j < 4;++j)
		{
			char a = s[i + j],b = t[j];
			if(a > b)	swap(a,b);
			int k = abs(a - b);
			// cout << s[i + j] << " " << t[j] << " " << k << " ";
			int k2 = abs(a - 'a' + 'z' - b) + 1;
			// cout << k2 << endl;
			cur += min(k,k2);
		}
		res = min(res,cur);
	}
	printf("%d\n",res);
    return 0;
}

B. Dima and a Bad XOR
题目大意:给定一个$n*m$的矩阵,现要求你每一行里选出一个元素,使他们的异或和不为$0$.如果任何的选择方案都无法得到一个不为$0$的答案,则输出无解.否则输出有解,以及实际的一个方案.
数据范围:
$1 \leq n,m \leq 500$
$0 \leq a_{i,j} \leq 1023$

这题乍看起来非常不可做,但是$xor$有一个特点:除非是两个相同的数异或,否则是不会出现$0$的.有一个很自然的想法就是:先直接把所有第一列的元素异或起来,如果已经是非零了,那就是合法的,如果是$0$的话,就去每一行找一个与那一行第一个数不同的数,就可以了.极端情况就是一个都没有,全是相同的,就只有是无解了.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
int a[N][N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	int res = 0;
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
			scanf("%d",&a[i][j]);
	
	for(int i = 1;i <= n;++i)	res ^= a[i][1];
	if(res > 0)
	{
		puts("TAK");
		for(int i = 1;i <= n;++i)	printf("1 ");
	}
	else
	{
		int ok = 0;
		for(int i = 1;i <= n;++i)
		{
			for(int j = 2;j <= m;++j)
			{
				if(a[i][j] != a[i][1])
				{
					ok = 1;
					puts("TAK");
					for(int k = 1;k <= n;++k)
					{
						if(k != i)	printf("1 ");
						else printf("%d ",j);
					}
					return 0;
				}
			}
		}
		puts("NIE");
	}
    return 0;
}

C. Problem for Nazar
题目大意:给定了两个有无穷个数的集合,前一个集合只有奇数,后一个只有偶数.奇数的从$1$开始,偶数的从$2$开始,并且两者都是连续的.现按如下方式构造一条序列:第一次从奇数集合里选择出$1$个数,第二次从偶数集合里选出$2$个数,第三次从奇数集合里选出$4$个数,第四次从偶数集合里选出$8$个数.即交替选择两个序列,并且每一次选的数量是上一次的两倍.例如前十位序列是:$1,2,4,3,5,7,9,6,8,10$.给定两个整数$l$和$r$,要求$l$到$r$内的和.由于结果很大,对$1*10^9+7$取模.

数据范围:
$1 \leq l,r \leq 10^{18}$

发现题目数据大的离谱,应该是有公式解,或者$log$级的,但是$log$级沾边的好像也就一个快速幂,派不上什么用场,先还是转换下问题:第一步应该还是比较好想的,既然是区间求和,显然就是一个前缀和的形式,我们需要求出一个$f(x)$,其值为$1~x$的和.最后的答案就是$f(r) - f(l - 1)$.

现在的问题就是怎么设计出这个$f(x)$,由于说这个数列看起来很牛逼,没什么下手的空间,尝试找到这个数列的分层的地方,因为他是一段一段拼接起来的,所以说对于一个位置来说,他前面的和由两个部分组成:偶数部分的和和奇数部分的和,这里的想法就是分解这个问题,然后想办法对两边较简单的问题下手再拼接.

可以想到:对于一个很简单的情况,就是说如果数列是完全连续的偶数序列或者奇数序列的时候,和是非常好算的:前$x$个偶数的和是$x * (x + 1)$,奇数是$x * x$.对某一位置$x$来说,只要能得到他前面有多少个偶数和多少个奇数,就可以分别计算两者的和了,换到原序列里去,可以发现对于某一位置$x$来说,虽然偶数序列或者奇数序列不一定是整段整段能拼完的,但是剩下的一部分也绝对是连续的,所以上面所说的对于某一个位置$x$知道前面偶数奇数个数就可以求和的性质对于这个序列来说也同样是适用的.

因此,对于$f(x)$来说,可以从长度为$1$开始乘,直到说接近到$x$为止,计算出每一段的奇数偶数的个数,最后按公式算出答案即可.不过要注意不光是答案,个数也是会爆$int$的,要注意取模.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100,MOD = 1e9+7;
ll a[N];

ll sum(ll r)
{
	ll res = 0;
	ll even = 0,odd = 0,len = 1;
	int k = 0;
	while(r > 0)
	{
		if(k == 0)	odd = (min(len,r) + odd) % MOD;
		else 		even = (min(len,r) + even) % MOD;
		r -= min(len,r);
		k ^= 1;
		len *= 2;
	}
	res = (res + even % MOD * (even + 1) % MOD) % MOD;
	res = (res + odd % MOD * odd % MOD) % MOD;
	return res;
}

int main()
{
	ll l,r;scanf("%lld%lld",&l,&r);
	printf("%lld",(sum(r) - sum(l - 1) + MOD) % MOD);
    return 0;
}

D. Stas and the Queue at the Buffet
题目大意:有$n$个人,每个人有两个值$a_i$和$b_i$.当一个人站在$j$位置时,他不爽的指数是$(j - 1) * a_i + (n - j) * b_i$.现在让你重新编排每一个人的位置,使总的不爽指数之和最小,输出最小值即可.

数据范围:
$1 \leq n \leq 10^5$
$1 \leq a_i,b_i \leq 10^8$

数据范围比较大,到了$10^5$,结合题目的说法,这很可能是一个排序题.先把题目给的信息拆一下,变成:$(a_i - b_i) * j + n * b_i - a_i$,发现这个表达式里,只有前面的$a_i - b_i$是和位置$j$有关的,后面的是一个常量.所以排序规则就比较明显了:按$a_i - b_i$倒序排即可.
不过这题数据范围应该是会爆$int$的,要注意

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 1e5+7;
pii a[N];
struct cmp
{
	bool operator()(const pii& a,const pii& b) const
	{
		return a.x - a.y > b.x - b.y;
	}
};
int main()
{
	int n;scanf("%d",&n);
	for(int i = 0;i < n;++i)	scanf("%d%d",&a[i].x,&a[i].y);
	sort(a,a + n,cmp());
	ll res = 0;
	for(int i = 0;i < n;++i)
		res += ((ll)a[i].x - a[i].y) * (i + 1) + (ll)a[i].y * n - a[i].x;
    printf("%lld",res);
    return 0;
}

E. Number of Components
这题在之前的abc 173F里是有的,也是一个样的做法由于有我就不详细说了.